package cxydmmszl.chapter05.t088;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

/**
 * <li style="color: red;">Prob</li>
 * 字符串的转换路径问题
 * <li style="color: green;">Desc</li>
 * 给定两个字符串，记为 start 和 to，再给定一个字符串列表 list，list 中一定包含 to，
 * list 中没有重复的字符串。所有的字符串都是小写的。规定 start 每次只能改变一个字符，
 * 最终的目标是彻底变成 to，但是每次变成新字符串必须在 list 中存在。
 * 请返回所有的最短的变换路径（按照字典序最小的顺序输出）。
 * <li style="color: green;">Input</li>
 * 输出包含多行，第一行包含一个整数 n（1≤n≤5000），代表 list 的中字符串的个数，
 * 第二行中包含两个字符串，分别代表 start 和 to。
 * 接下来 n 行，每行一个字符串，代表 lis[i]（保证字符串长度都为 3）。
 * <li style="color: green;">Output</li>
 * 如果存在转换的路径，请先输出 “YES”，然后按照字典序最小的顺序输出所有路径。
 * 如果不存在请输出“NO”。
 * <li style="color: blue;">Link</li> CD123
 *
 * @author habitplus
 * @since 2021-09-11 21:12
 */
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] ss = br.readLine().split(" ");
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(br.readLine());
        }
        br.close();

        List<List<String>> res = findMinPaths(ss[0], ss[1], list);
        if (res.size() == 0) {
            System.out.println("NO");
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append("YES\n");
            for (List<String> r : res) {
                sb.append(String.join(" -> ", r)).append("\n");
            }
            System.out.println(sb.toString());
        }
    }

    private static List<List<String>> findMinPaths(String start, String to, List<String> list) {
        list.add(start);
        // list 中的每个字符串建立下一步的 map 表
        HashMap<String, List<String>> nexts = getNexts(list);
        // 求每个字符到 start 的最短距离
        HashMap<String, Integer> dis = getDistances(start, nexts);

        LinkedList<String> pathList = new LinkedList<>();
        List<List<String>> res = new ArrayList<>();

        getShortestPaths(start, to, nexts, dis, pathList, res);
        return res;
    }

    private static void getShortestPaths(String cur, String dest,
                                         Map<String, List<String>> nexts,
                                         Map<String, Integer> distances,
                                         LinkedList<String> pathList,
                                         List<List<String>> res) {
        pathList.add(cur);
        if (dest.equals(cur)) {
            // 找到一条路径
            res.add(new LinkedList<>(pathList));
        } else {
            for (String next : nexts.get(cur)) {
                if (distances.get(next) == distances.get(cur) + 1) {
                    getShortestPaths(next, dest, nexts, distances, pathList, res);
                }
            }
        }
        pathList.pollLast();
    }

    private static HashMap<String, Integer> getDistances(String start, HashMap<String, List<String>> nexts) {
        HashMap<String, Integer> distances = new HashMap<>();
        Queue<String> que = new LinkedList<>();
//        HashSet<String> vis = new HashSet<>();
        String cur;
        int d = 0;

        que.offer(start);
//        vis.add(start);
        distances.put(start, d);

        while (!que.isEmpty()) {
            d++;
            for (int i = que.size(); i > 0; i--) {
                cur = que.poll();
                for (String str : nexts.get(cur)) {
                    if (!distances.containsKey(str)) {
                        distances.put(str, d);
                        que.offer(str);
//                        vis.add(str);
                    }
                }
            }
        }

        return distances;
    }

    private static HashMap<String, List<String>> getNexts(List<String> list) {
        HashMap<String, List<String>> map = new HashMap<>();
        Set<String> set = new HashSet<>(list);

        for (String s : set) {
            map.put(s, getNext(s, set));
        }

        return map;
    }

    private static List<String> getNext(String s, Set<String> dict) {
        List<String> resList = new ArrayList<>();
        char[] chs = s.toCharArray();
        String tmp;
        char c;
        for (char w = 'a'; w <= 'z'; w++) {
            for (int i = 0; i < chs.length; i++) {
                if (chs[i] != w) {
                    c = chs[i];
                    chs[i] = w;
                    tmp = new String(chs);
                    if (dict.contains(tmp)) {
                        resList.add(tmp);
                    }
                    chs[i] = c;
                }
            }
        }
        return resList;
    }
}
